# Definition for a binary tree node.
from typing import Optional

from python.mypackage import TreeNode

class Solution:
    """
    方法： maxDepth 递归实现
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        int: 二叉树的最大深度
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(H)，其中 H 为二叉树的高度。递归调用的栈空间取决于二叉树的高度。
    """
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        l_depth = self.maxDepth(root.left)  
        r_depth = self.maxDepth(root.right)
        return max(l_depth, r_depth) + 1

    """
    方法： maxDepth1 迭代实现，使用队列进行层序遍历
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        int: 二叉树的最大深度
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(W)，其中 W 为二叉树的最大宽度。在最坏情况下，队列中会存储一层中的所有节点。
    """

    def maxDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp = []
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp;
            res += 1
        return res